#include <bits/stdc++.h>
using namespace std;

/*
1504. 统计全 1 子矩形
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个 m x n 的二进制矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。

 

示例 1：



输入：mat = [[1,0,1],[1,1,0],[1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。
示例 2：



输入：mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。

 

提示：

1 <= m, n <= 150
mat[i][j] 仅包含 0 或 1
*/

// 法一
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        // 单调栈处理递增情况
        if (mat.empty() || mat[0].empty()) return 0;// 处理空矩阵边界情况
        
        int m = mat.size();       // 矩阵行数
        int n = mat[0].size();    // 矩阵列数
        
        // 预处理：每一行转换成高度数组（当前位置向上连续1的数量）
        // 注意：i从1开始，避免i=0时访问mat[-1][j]导致越界
        for (int i = 1; i < m; ++i) {  // 修正：i从1开始（i=0无上行可累加）
            for (int j = 0; j < n; ++j) {
                // 仅当当前位置为1时，才累加上行同列的高度（i-1此时有效）
                mat[i][j] += (mat[i][j] == 1 ? mat[i - 1][j] : 0);
            }
        }
        int totalCnt = 0;

        // 逐行迭代计算
        for (int i = 0; i < m; i++) totalCnt += cntSubmatInRow(mat[i]);

        return totalCnt;
    }

    // 单调栈辅助函数：计算当前行高度数组对应的矩形数量
    int cntSubmatInRow(const vector<int>& heights) {
        int n = heights.size();
        vector<int> sum(n, 0);
        vector<int> stack;      // 严格单调递增栈（存储索引）
        for (int i = 0; i < n; i++) {
            // 弹出栈中高度 >= 当前高度的元素，维持栈的递增特性
            while (!stack.empty() && heights[stack.back()] >= heights[i])       stack.pop_back();

            if (!stack.empty()) {
                // 栈非空：取栈顶（左侧第一个更矮的柱）计算
                int prevIdx = stack.back();
                sum[i] = sum[prevIdx] + heights[i] * (i - prevIdx);
            } else {
                // 栈为空：当前柱是左侧最矮的，计算从0到i的所有宽度
                sum[i] = heights[i] * (i + 1);
            }
            // 当前索引入栈
            stack.push_back(i);
        }
        int rowTotal = 0;
        for (int s : sum)   rowTotal += s;

        return rowTotal;
    }
};

// 法二
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        // 处理空矩阵边界情况
        if (mat.empty() || mat[0].empty()) return 0;
        
        int rows = mat.size();       // 矩阵行数
        int cols = mat[0].size();    // 矩阵列数
        
        vector<int> height(cols, 0); // 直方图高度数组，大小应为列数cols
        int ans = 0;
        
        // 逐行遍历（行数为rows，所以i < rows）
        for (int i = 0; i < rows; ++i) {
            // 更新当前行的高度数组（列数为cols，j < cols）
            for (int j = 0; j < cols; ++j) {
                height[j] = mat[i][j] ? height[j] + 1 : 0;
            }
            
            // 计算当前直方图中的全1子矩形数量
            for (int j = 0; j < cols; ++j) {
                if (height[j] == 0) continue;
                
                int minHeight = height[j];
                ans += minHeight; // 宽度为1的矩形
                
                // 向左扩展
                for (int k = j - 1; k >= 0; --k) {
                    if (height[k] == 0) break;
                    
                    minHeight = min(minHeight, height[k]);
                    ans += minHeight;
                }
            }
        }
        
        return ans;
    }
};

// 法三
// stack效率高于vector  
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        // h[j]：第j列向上（包括当前行）连续1的高度（直方图的柱高）
        // dp[j]：以当前行第j列为右边界的所有全1子矩形数量
        vector<int> h(n, 0), dp(n, 0);
        int ans = 0;  // 累计所有全1子矩形的总数
        
        // 逐行处理矩阵，每一行对应一个直方图
        for (int i = 0; i < m; ++i) {
            // 第一步：更新当前行的高度数组h
            for (int j = 0; j < n; ++j) {
                // 若当前位置是1，高度在之前基础上加1；否则重置为0
                h[j] = mat[i][j] ? h[j] + 1 : 0;
            }
            
            // 第二步：用单调栈计算当前直方图中所有全1子矩形数量
            stack<int> s;  // 单调递增栈，存储列索引（栈中索引对应的h值严格递增）
            for (int j = 0; j < n; ++j) {
                // 弹出栈中高度 >= 当前h[j]的元素
                // 原因：当前柱更矮，之前更高的柱无法与当前柱形成更高的矩形，需移除
                while (!s.empty() && h[s.top()] >= h[j]) {
                    s.pop();
                }
                
                // 计算dp[j]：以第j列为右边界的矩形数量
                if (h[j] == 0) {
                    // 当前柱高为0，无法形成任何矩形，dp[j]为0
                    dp[j] = 0;
                } else if (s.empty()) {
                    // 栈为空：当前柱是左侧所有柱中最矮的
                    // 可形成的矩形宽度为0~j（共j+1种），每种宽度对应高度为h[j]
                    dp[j] = h[j] * (j + 1);
                } else {
                    // 栈非空：栈顶是左侧第一个高度 < h[j]的柱（记为k）
                    // dp[k]：左侧以k为右边界的所有矩形（高度均 < h[j]，可与当前柱组合）
                    // h[j]*(j - k)：以h[j]为高，宽度从k+1到j的矩形（共j-k种宽度）
                    dp[j] = dp[s.top()] + h[j] * (j - s.top());
                }
                
                // 累加当前列贡献的矩形数量到总结果
                ans += dp[j];
                // 当前列索引入栈，维持栈的单调递增特性
                s.push(j);
            }
        }
        
        return ans;
    }
};